The present invention relates to arrangements, a system and a method within transmission of digital data. At transmission of information, e.g. data communications and wireless communications, errors are substantially always produced when signals are transferred over a channel from the transmitting side to the receiving side. Coding is often used as a protection against distorsion when data is transported over a channel. The present invention particularly relates to a receiving arrangement for receiving a digitally coded data signal transported over a channel. The invention also relates to a system for transferring digitally coded data signals over channels. Still further the invention relates to an error detecting arrangement, particularly a so called CRC (Cyclic Redundancy Check) decoder for detecting errors in a received CRC-coded data signal. The invention also relates to a method of detecting errors in a CRC-coded digital data signal.
One particular case when coding is used as a protection against distorsion is within mobile communications wherein a signal is transferred by radio between a base station and a mobile telephone. The longer the distance, the more the radio signal is attenuated and it also suffers from distorsion in the form of fading produced by interference, so called multiple fading, which means that a signal can take many different ways from one point to another in that it is reflected for example against buildings, etc.
In some digital mobile communication standards coding in two steps has been introduced in order to give an acceptable protection against loss of information. On the transmitting side an error detecting CRC-coder is introduced and as a second step an error correcting block coding device is introduced. A signal is supposed to comprise a number of sequences wherein each sequence is divided into a number of blocks, each of which blocks in turn comprises a number of bits. The error correcting device operates block-wise.
On the receiving side an error correcting decoder which decodes blocks of the total sequence forms a first step. In a second step an error detecting CRC-decoder is implemented to establish whether the error correcting decoder has made any erroneous decisions. The error detecting decoder operates on the entire sequence which, as referred to above, comprises a number of blocks. When the error detecting CRC-decoder detects that the decoded sequence is wrong, it is requested that the sequence be retransmitted. However, this may be very time consuming since several attempts may be necessary. Furthermore, signalling is required between the sending and the receiving side in order to administrate the retransmissions and this demands capacity which otherwise could have been used for useful transmission of information. What is needed is therefore a way to, as fast as possible, find the correct sequence and thus avoid, or at least reduce, retransmission. One known way of handling this problem is to make the error correcting block decoder provide a plurality of alternative suggestions which are tested by the error detecting decoder. The probability that one of the suggestions is correct will then be increased. It is, however, difficult to select candidates. The error correcting decoder is only capable of testing a limited number of alternative solutions. Furthermore, if too many alternatives are tested, the risk increases that an erroneous suggestion is accepted. Alternatives can be selected if each data bit has an attribute in the form of so called soft information, which is a measure on the probability that the chosen sign (zero or one) is correct. Candidates are selected through inverting bits with the lowest soft information, i.e. the bits which are the most likely to be wrong, are questioned first. One method of using soft information is the second algorithm of Chase. This is discussed in xe2x80x9cA class of algorithms for decoding block codes with channel measurement informationxe2x80x9d, IEEE Trans. Inform. Theory, vol. IT-18, pages 170-182, January., 1972, by D. Chase. In xe2x80x9cImproved decoding of a concatenated code using soft decoding techniquesxe2x80x9d, A Master of Science Thesis, dept. of Information Theory, Chalmers University of Technology, Gothenburg, Sweden, by M. Fahami and P. Flodin, December, 1995, the method has been further evaluated. Both these documents are herewith incorporated herein by reference. The soft information method consists in that a number of, for example M, alternatives are calculated for each block in the sequence. A number of blocks, N, are selected out of the total number of blocks. The N blocks should be the poorest blocks as far as this can be concluded, i.e. the blocks relating to which the uncertainty is the highest. The total sequence is then produced and consists of the permutations of the alternatives. Totally, there are thus MN alternative sequences to be tested. It should, however, be noted that there are a number of blocks that never have changed (the total sum minus N).
The error detecting CRC-decoder is applied in such a way that the total block decoded sequence is multiplied by the parity check matrix (H) of the CRC-polynomial. This can be realized as the sequence being shifted through a shift register, which e.g. may be implemented as hardware or as software. When the whole sequence has been shifted through the shift register, the content of the shift register is read out. This forms the syndrome of the decoding operation. If the syndrome only comprises zeros, the sequence is accepted, otherwise it is rejected. The CRC-coding can be defined through the original sequence being shifted through a shift register in which the cells have a starting position different from zero. In this manner the shifting operation is made non-linear.
This can, however, be seen as, starting from an initial state in which there are zeros in all cells, a preamble is shifted in which generates the defined starting state and then shifting in the sequence to be coded. On the decoding side this corresponds to the preamble being shifted in first followed by the sequence to be decoded. If a preamble is required, the parity check matrix is increased by as many rows as the preamble comprises. However, the number of the operations is high and, in addition thereto, many shifts are required and such operations are generally long and demanding operations, which in turn reduces the performance or requires much power. A consequence thereof may for example be that less alternatives than actually would be needed are tested.
What is needed is, therefore, a receiving arrangement for receiving a digitally coded data signal transported over a channel which includes means for error correction and detection, which only requires a limited number of advanced and demanding calculation operations in order to find a correctly transmitted sequence and which particularly requires fewer operations than hitherto known arrangements do. Particularly an arrangement is needed through which it is possible to save power and to lower the fabrication costs. An arrangement is also needed through which a high performance can be provided and through which a correctly transmitted signal efficiently can be found without requiring a high number of demanding operations, much power, etc.
A system for transferring digitally coded data signals over channels from a transmitting side to a receiving side is also needed, through which the above mentioned objects are achieved, i.e. wherein a correctly sent sequence easily and quickly can be found and in which as few retransmissions as possible are needed. An error detecting CRC-decoder for detecting errors in a received CRC-coded digital data signal which has been decoded in error correcting means is also needed, through which the above mentioned objects can be achieved.
Still further, a method of detecting errors in a CRC-coded digital data signal sequence is also needed, through which the detection can be performed fast and in an efficient and reliable manner and requiring as few long and complicated calculation operations as possible, and through which the performance can be kept at a high level. Still further, a method is needed through which the above mentioned objects are achieved and which is cost effective.
Therefore, a receiving arrangement as referred to above is provided which comprises error detecting means and storing means for storing information relating to the possible, different, block alternatives, wherein the error detecting means comprises a differential CRC-decoder. Said differential decoder includes first decoding means for decoding a sequence of blocks using a reference sequence to provide a reference syndrome. The second decoding means is used for decoding selected, alternative, differential blocks of the sequence, which alternatives are obtainable via the error correcting means. The differential blocks are calculated as the difference between the corresponding block of the reference sequence and each alternative block respectively, to provide differential syndromes. Then the sum of the reference syndrome and the respective differential syndrome is taken to provide resulting syndromes. The respective resulting syndromes are used to establish whether an alternative is correctly received or not.
Particularly, the reference syndromes are calculated through multiplying the reference sequence by a parity check matrix of the CRC-polynomial and the differential blocks are calculated as the difference (modulo 2) of the block of the reference sequence and the respective selected block alternatives. In a particular implementation the differential syndromes are generated through multiplication of the differential blocks by the corresponding part of the parity check matrix of the CRC-polynomial.
In a particular, advantageous, implementation the first decoding means comprises a first shift register and the reference syndrome is calculated through shifting the reference sequence once through said first shift register. Particularly, the second decoding means comprises a second shift register with parameters that can be loaded with values tabulated in the storing means for different positions according to the different alternatives and the differential blocks are shifted through said second shift register to provide the differential syndromes. Particularly, for a sequence comprising K blocks, of which N blocks are selected to have M alternatives, the number of calculation operations are K shifts to provide the reference syndrome, Nx (Mxe2x88x921) shifts to calculate the differential syndromes and MN additions (modulo 2) to calculate the resulting syndromes. The first and second decoding means may be implemented as hardware or software according to different embodiments. Particularly, the second shift register is used differently for each block position, which is a result of the above statements, and it provides for forward feeding as well as backward feeding of data, the coefficients of the CRC-polynomial being used for backward feeding and individual vectors of the H-matrix of the CRC-polynomial being used for forward feeding. Particularly, given rows of the H-matrix are stored in the storing means, e.g. a table, and the rows are given by how the original sequence is divided into blocks.
Therefore, also a system as referred to above is provided, which includes a number of transmitting arrangements and a number of receiving arrangements, which transmitting arrangements comprise error detecting CRC-coding means and error correcting block coding means through which a signal is transmitted to a receiving arrangement including error correcting means finding a number of block alternatives of a sequence which alternatives are provided to error detecting CRC-decoding means. The error detecting CRC-decoding means consists of a differential CRC-decoder including first and second decoding means. Furthermore, storing means are provided. The first decoding means are used for decoding a sequence of blocks using a reference sequence to provide a reference syndrome, whereas the second decoding means are used for decoding alternative differential blocks of the original sequence input to the receiving means. The alternatives are provided by the error detecting means and information about the different alternatives is contained in the storing means. The differential blocks are calculated using the second decoding means as the difference between the corresponding block of the reference sequence and each respective alternative block and the respective differential syndromes are provided for by multiplication by the appropriate parts of the parity check matrix of the CRC-polynomial. Resulting syndromes are calculated as the sum (modulo 2) of the reference syndrome and the respective differential syndromes.
Thus, the reference syndrome is calculated through multiplying the reference sequence by a parity check matrix of the CRC-polynomial and the differential syndromes are calculated as the difference (modulo 2) of the block of the reference sequence and the respective selected block alternatives multiplied by the relevant rows of the parity check matrix. Particularly, the first decoding means comprises a first shift register and the reference syndromes are calculated through shifting the reference sequence once through said first shift register. The second decoding means particularly is implemented as a second shift register with loadable parameters which are given values which are tabulated in the storing means for different positions according to the different alternatives as provided by the error correcting means. Differential blocks are then shifted through the second shift register to provide the differential syndrome.
Therefore, an error detecting arrangement is also provided, which comprises a CRC-decoder. According to the invention the CRC-decoder is differential and comprises first decoding means, second decoding means and storing means, as already discussed above.
Further yet, a method of detecting errors in a CRC-coded digital signal is provided. The method includes the steps of dividing the data signal sequence into blocks each comprising a number of bits; decoding blocks of the sequence in an error correcting decoder and the error correcting decoder providing a number of block alternatives to error detecting means. The method further includes the steps of: providing information, e.g. parameter values, relating to the block alternatives to storing means; storing information about said alternatives in said storing means; providing the alternatives to a differential error detecting decoder; using a reference sequence in first decoding means of the differential decoder to provide a reference syndrome; decoding differential alternative blocks using the block alternatives and information relating thereto contained in the storing means by calculating the difference between the reference block and the respective differential blocks to provide differential syndromes; adding a number (between 1 and N) of differential syndrome(s) (not two from the same block position) to the reference syndrome to obtain a number of resulting syndromes respectively; and, if the value of a respective resulting syndrome is zero, a block alternative is accepted. Particularly advantageous embodiments or alternatives are given by the subclaims.
It is an advantage of the invention that the number of long and complicated calculations are considerably reduced and to a great extent replaced by shorter and simpler calculative operations. It is particularly an advantage of the invention that a high performance can be provided and in that the sufficient number of alternatives easily can be tested, thus providing a reliable arrangement/method. It is a particular advantage of the invention that through the simplification of the calculative operations, power can be saved and in a particular embodiment may for example the number DSPs (Digital Signal Processor) that are needed, be reduced.